package com.sheng.leetcode.year2023.month03.day08;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/03/08
 * <p>
 * 剑指 Offer 47. 礼物的最大价值<p>
 * <p>
 * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。<p>
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。<p>
 * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？<p>
 * <p>
 * 示例 1:<p>
 * 输入:<p>
 * [<p>
 * [1,3,1],<p>
 * [1,5,1],<p>
 * [4,2,1]<p>
 * ]<p>
 * 输出: 12<p>
 * 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物<p>
 * <p>
 * 提示：<p>
 * 0 < grid.length <= 200<p>
 * 0 < grid[0].length <= 200<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof">剑指 Offer 47. 礼物的最大价值</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCodeMaxValue {

    @Test
    public void test01() {
        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        System.out.println(new Solution().maxValue(grid));
    }
}

class Solution {
    public int maxValue(int[][] grid) {
        // 对于二维数组，当走到 (i, j) 这一步时，上一步可能是 (i - 1, j) 或 (i, j - 1)两种可能中价值最高的一步
        // 假设走到 (i, j) 这一步时的礼物价值为 f(i, j) ，那么 f(i, j) = Math.max(f(i - 1, j), f(i, j - 1)) + g(i, j) 其中 g(i, j) 为当前位置的礼物价值
        int m = grid.length;
        int n = grid[0].length;
        int[][] ints = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = i + 1, y = j + 1;
                ints[x][y] = Math.max(ints[x][j], ints[i][y]) + grid[i][j];
            }
        }
        return ints[m][n];
    }
}
